The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change an LSP representing the change is flooded through the network by each node adjacent the change, each node receiving the LSP sending it to each adjacent node.
As a result, when a data packet for a destination node arrives at a node the node identifies the optimum route to that destination and forwards the packet to the next node (“next hop”) along that route. The next node repeats this step and so forth.
The SPF algorithm comprises an implementation of the Dijkstra algorithm. The algorithm is well understood by the skilled reader and is well documented in pre-existing documentation and therefore is not described in detail here but only in summary, for the purposes of clarity.
In general a constructing node calculates its least cost (shortest path) routes to each other node on the network from its LSDB. To do this, all nodes on the network are divided into three categories, unknown (UNK), tentative or candidate (TENT) and known (PATHS). For each node the cost of reaching that node from the constructing node, and the interface along which it is reached at that cost (representing the next hop) are stored. Initially the constructing node is assigned to category TENT and all other nodes are assigned to UNK. The algorithm then carries out repeatedly the step of moving the lowest cost node in TENT to PATH and moving all neighbours of that lowest cost node together with their cost via the corresponding interface from the constructing node to TENT. As a result, in the first step the constructing node is moved to PATH and each of its neighbours to TENT. In the next step the lowest cost node in TENT is moved into PATH and its neighbours are moved into TENT. As a result the nodes in UNK and TENT gradually deplete until all nodes have been moved to PATH. As a result PATH comprises a list of the lowest cost interface (or next hop) for routing data from the constructing node to each other node.
As a result the spanning tree is constructed rooted at the constructing node and with branches to each next hop, that is each neighbor node. Each neighbour node then has branches to each of its next hops which the constructing node would reach via the neighbor node as shortest path, and the tree expands accordingly providing a single route to each node reachable from the constructing node. As a result it is possible to derive from the spanning tree which of the constructing node's neighbor nodes serves as next hop for any destination node within the SPT, allowing population of the FIB and hence RIB with appropriate forwarding/routing information. It will be noted that the SPT will only carry information for nodes which are reachable from the constructing node and so may not have information for all nodes in the LSDB if some of those nodes are unreachable.
When the network topology changes, for example a component such as a link or node changes either by variation in a metric such as link cost or by addition or failure of a node then conventionally the SPT must be recomputed from scratch using the SPF algorithm. However in one known approach described in co-pending patent application Ser No. 09/687,009, filed 12 Oct. 2000, entitled “Method and System for Accelerating Route Calculation in Link State Routing Protocols” of John Harper, SPF has been extended using the incremental SPF (I-SPF) optimization which speeds up the routing computation by updating the SPT rather than recomputing it from scratch at each topology change. In particular I-SPF recognizes that only the affected part of the SPT requires recomputation. Using I-SPF, the nodes in the affected branch (for example all nodes “downstream” of a failed node or link component) are identified and reattached to the remaining, unchanged part of the tree for example by placing the affected nodes back into TENT and rerunning the SPF algorithm in respect of those nodes until they are all attached.
However it is found that I-SPF improvement may not be significant when processing certain network events and in particular there may be cases where a topology change requires more computation and hence CPU time if computed by I-SPF rather than a full SPF recomputation. In particular such events comprise link or node failure events, especially when the failure is close to the computing router that is constructing the SPT. This is because the entire branch of the SPT attached to the failed component must be reattached somewhere else in the SPT, and the size of the affected branch tends to increase the closer the failure is to the constructing node, increasing the work carried out by the I-SPF algorithm correspondingly.
To compensate for this, in one known approach, where I-SPF has been configured on a router, a full SPF is nonetheless executed for local failures at the computing router. However it is possible that remote failures may still require significant I-SPF computation whereas local failures may be repaired by I-SPF very efficiently.